package sort;

import java.util.HashMap;
import java.util.LinkedList;

public class RadixSort implements ISort{

	private HashMap<Integer, LinkedList<Integer>> bucket = new HashMap<Integer, LinkedList<Integer>>();

	public RadixSort() {
		for (int i = 0; i < 10; i++) {
			bucket.put(i, new LinkedList<Integer>());
		}
	}

	public void clearBucket() {
		for (int i = 0; i < 10; i++) {
			bucket.put(i, new LinkedList<Integer>());
		}
	}

	public void sort(int[] arr) {
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		int highestDigit = 0;
		while (max / (int) Math.pow(10, highestDigit) != 0) {
			highestDigit++;
		}
		highestDigit--;//位数会多加一位
		
		for (int i = 0; i <= highestDigit; i++) {
			for (int j = 0; j < arr.length; j++) {
				int digit = getDigit(arr[j], i);
				bucket.get(digit).add(arr[j]);
			}
			int pos = 0;
			for (int m = 0; m < bucket.size(); m++) {
				for (int n = 0; n < bucket.get(m).size(); n++) {
					arr[pos++] = bucket.get(m).get(n);
				}
			}
			clearBucket();
		}

	}

	/**
	 * 获取某位上的数字
	 * 
	 * @param value 原数字
	 * @param i     0个位，1十位。。。
	 * @return
	 */
	public int getDigit(int value, int i) {
		int bit = value / (int) Math.pow(10, i) % 10;
		return bit;
	}

	public static void main(String[] args) {
		int[] arr = { 53, 3, 542, 748, 14, 214, 154, 63, 616 };
		RadixSort radixSort = new RadixSort();
		radixSort.sort(arr);
		ISort.printArr(arr);
	}

}